package com.heima.algorithm.sort;

/**
 * <strong>希尔排序</strong>
 * <p>思想：分组实现插入排序，每组元素间隙成为gap，元素相邻时gap为1，每轮插入排序结束后，gap就会缩小，直到gap = 1完成排序，优点在于步子跨得大，让元素更快的交换到最终位置</p>
 * @author 勾新杰
 * @version 1.0
 * @date 2024/9/30 16:03
 */
public class ShellSort {
    //（1）基于比较的排序算法
    //（2）最好情况：O(NlogN)，最坏情况：O(N^2)，平均情况：O(NlogN)，空间复杂度：O(1)，稳定：是，思想：插入
    //（3）gap序列的构造有多种方式，不同方式处理的数据复杂度可能不同

    /**
     * 希尔排序
     * @param arr 待排序数组
     */
    public static void shellSort(int[] arr) {
        // 每次根据gap对arr进行分组再对各个分组进行插入排序，gap初始值为数组长度整除2，直到gap = 1，也就是相邻情况，就是整个数组为一个分组
        // 分析可得，数组一次会分成gap个组，（第一个出现循环的是gap，那么0 ~ gap - 1都是各个分组的第一个元素），所以gap = 1时只有一个分组，就是整个数组
        for (int gap = arr.length >> 1; gap >= 1; gap >>= 1){
            // 这里i初始为gap是因为默认各个分组的第一个元素是排序好的，又0+gap是第一次出现循环的索引，所以gap++实际上就是在对每个分组进行插入排序
            for (int i = gap; i < arr.length; i++){
                // 待插入值
                int inserted = arr[i];
                // 插入索引
                int index = i;
                // 寻找插入索引，寻找时要保证index始终位于当前分组内，其次每次循环index会减一个gap，而index最小是0，则进入循环时要求index最小是gap
                while (index >= gap && arr[index - gap] > inserted){
                    arr[index] = arr[index - gap]; // 相比于插入排序，步子迈的更大，可见少了很多赋值操作
                    index -= gap;
                }
                // 当找到的插入位置不是i，则插入
                if (index != i){
                    arr[index] = inserted;
                }
            }
        }
    }
}
